{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Mice and Cheese"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: miceAndCheese"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #老鼠和奶酪"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有两只老鼠和&nbsp;<code>n</code>&nbsp;块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。</p>\n",
    "\n",
    "<p>下标为 <code>i</code>&nbsp;处的奶酪被吃掉的得分为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果第一只老鼠吃掉，则得分为&nbsp;<code>reward1[i]</code>&nbsp;。</li>\n",
    "\t<li>如果第二只老鼠吃掉，则得分为&nbsp;<code>reward2[i]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个正整数数组&nbsp;<code>reward1</code>&nbsp;，一个正整数数组&nbsp;<code>reward2</code>&nbsp;，和一个非负整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回第一只老鼠恰好吃掉 <code>k</code>&nbsp;块奶酪的情况下，<strong>最大</strong>&nbsp;得分为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2\n",
    "<b>输出：</b>15\n",
    "<b>解释：</b>这个例子中，第一只老鼠吃掉第 2&nbsp;和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。\n",
    "总得分为 4 + 4 + 3 + 4 = 15 。\n",
    "15 是最高得分。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>reward1 = [1,1], reward2 = [1,1], k = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>这个例子中，第一只老鼠吃掉第 0 和 1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。\n",
    "总得分为 1 + 1 = 2 。\n",
    "2 是最高得分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == reward1.length == reward2.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= reward1[i],&nbsp;reward2[i] &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [mice-and-cheese](https://leetcode.cn/problems/mice-and-cheese/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [mice-and-cheese](https://leetcode.cn/problems/mice-and-cheese/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,3,4]\\n[4,4,1,1]\\n2', '[1,1]\\n[1,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        \n",
    "        q1, q2 = [], []\n",
    "        \n",
    "        for i, (a, b) in enumerate(zip(reward1, reward2)):\n",
    "            if a >= b:\n",
    "                heappush(q1, (b-a, -a, i))\n",
    "            else:\n",
    "                heappush(q2, (a-b, -b, i))\n",
    "        \n",
    "        ans = 0\n",
    "        while k and q1:\n",
    "            ans += -heappop(q1)[1]\n",
    "            k -= 1\n",
    "        \n",
    "        if not k:        \n",
    "            for _, _, i in q1 + q2:\n",
    "                ans += reward2[i]\n",
    "\n",
    "        else:\n",
    "            for _ in range(len(q2) - k):\n",
    "                ans += -heappop(q2)[1]\n",
    "            \n",
    "            while q2:\n",
    "                ans += reward1[heappop(q2)[2]]\n",
    "            \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        if n == k:\n",
    "            return sum(reward1)\n",
    "        if k == 0:\n",
    "            return sum(reward2)\n",
    "        score = []\n",
    "        ans = 0\n",
    "        for x,y in zip(reward1,reward2):\n",
    "            heappush(score,x-y)\n",
    "            ans += x\n",
    "            if len(score) > k:\n",
    "                ans -= heappop(score)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        a=sum(reward1)+sum(reward2)\n",
    "        n=len(reward1)\n",
    "        for i in range(n):\n",
    "            reward1[i]=reward1[i]-reward2[i]\n",
    "        print(reward1)\n",
    "        reward1.sort()\n",
    "        b=sum(reward1[n-k:])-sum(reward1[:n-k])\n",
    "        print(a,b)\n",
    "        return (a+b)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        if k == n:\n",
    "            return sum(reward1)\n",
    "        l = [reward1[i] - reward2[i] for i in range(n)]\n",
    "        l.sort(reverse=True)\n",
    "        dp = [0] * n\n",
    "        s1 = sum(reward2)\n",
    "        ans = s1\n",
    "        for i in range(1, k+1):\n",
    "            ans += l[i - 1]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        diff = [0] * n\n",
    "        for i in range(n):\n",
    "            diff[i] = reward1[i] - reward2[i]\n",
    "\n",
    "        diff.sort(reverse = True)\n",
    "\n",
    "        point = sum(reward2)\n",
    "\n",
    "        for i in range(k):\n",
    "            point += diff[i]\n",
    "\n",
    "        return point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        diffs = [i-j for i, j in zip(reward1, reward2)]\n",
    "        sum2 = sum(reward2)\n",
    "        diffs.sort(reverse=True)\n",
    "        for i in range(k):\n",
    "            sum2 += diffs[i]\n",
    "        return sum2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        for i in range(n):\n",
    "            reward1[i] -= reward2[i]\n",
    "        index = [i for i in range(n)]\n",
    "        index.sort(key=lambda x: reward1[x], reverse=True)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i < k:\n",
    "                ans += reward1[index[i]] + reward2[index[i]]\n",
    "            else:\n",
    "                ans += reward2[index[i]]\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            total += reward2[i]\n",
    "            reward1[i] -= reward2[i]    # 如果一个地方由第一只老鼠吃，总数的变化\n",
    "        return sum(nlargest(k, reward1)) + total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        dis = [i-j for i,j in zip(reward1, reward2)]\n",
    "        return sum(sorted(dis, reverse=True)[:k]) + sum(reward2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        diff = sorted([x1 - x2 for x1, x2 in zip(reward1, reward2)], reverse=True)\n",
    "        return sum(diff[:k] + reward2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        dis = [i-j for i,j in zip(reward1, reward2)]\n",
    "        heapq.heapify(dis)\n",
    "        dis = heapq.nlargest(k, dis)\n",
    "        # res = sorted(zip(dis, range(0,len(reward1))), reverse=True)\n",
    "        return sum(dis) + sum(reward2)\n",
    "        index = set([j for _,j in res[:k]])\n",
    "        return sum([reward1[i] if i in index else reward2[i] for i in range(0, len(reward1))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n,ans=len(reward1),0\n",
    "        for i in range(n):\n",
    "            x=max(reward1[i],reward2[i]);ans+=x\n",
    "            reward1[i]=(reward1[i]-x,reward1[i]-reward2[i])\n",
    "        reward1.sort(reverse=True)\n",
    "        for i in range(k):ans+=reward1[i][0]\n",
    "        for i in range(k,n):\n",
    "            if(reward1[i][0]==0):ans-=reward1[i][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n=len(reward1)\n",
    "        # mul=[reward1[i]-reward2[i] for i in range(n)]\n",
    "        l=[i for i in range(n)]\n",
    "        l.sort(key=lambda i:reward2[i]-reward1[i])\n",
    "        score=sum([reward1[i] for i in l[:k]])+sum(reward2[i] for i in l[k:])\n",
    "        return score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        if n == k :\n",
    "            return sum(reward1)\n",
    "        if k == 0:\n",
    "            return sum(reward2)\n",
    "        ans = 0\n",
    "        dp = []\n",
    "        for i in range(n):\n",
    "            dp.append([reward1[i] - reward2[i],i])\n",
    "        dp = sorted(dp,key = lambda x: x[0],reverse = True)\n",
    "\n",
    "        size = 0\n",
    "        print(dp)\n",
    "        for i in dp:\n",
    "            if size < k:\n",
    "                ans += reward1[i[1]]\n",
    "                size += 1\n",
    "            else:\n",
    "                ans += reward2[i[1]]\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        decrease = [reward1[i] - reward2[i] for i in range(n)]\n",
    "        new_index = sorted(range(n), key=lambda x: -decrease[x])\n",
    "        # 首先进行初始化满意度为0\n",
    "        satisfaction = 0\n",
    "\n",
    "        # 进行便利\n",
    "        for i in range(k):\n",
    "            satisfaction = satisfaction + reward1[new_index[i]]\n",
    "\n",
    "        for j in range(k, n):\n",
    "            satisfaction = satisfaction + reward2[new_index[j]]\n",
    "\n",
    "        return satisfaction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, \n",
    "        reward1, \n",
    "        reward2, \n",
    "        k: int) -> int:\n",
    "\n",
    "        a=[(i-j,i,j) for i,j in zip(reward1,reward2)]\n",
    "        a.sort(reverse=True)\n",
    "        res=0\n",
    "        for i in range(k):\n",
    "            res+=a[i][1]\n",
    "        for i in range(k,len(a)):\n",
    "            res+=a[i][2]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n=len(reward1)\n",
    "        nums=[(reward1[i]-reward2[i],reward1[i],reward2[i])  for i in range(n)]\n",
    "        res=0\n",
    "        nums.sort(reverse=True)\n",
    "        for i,(_,val1,val2) in enumerate(nums):\n",
    "            res+=val1 if i<k else val2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        a = sorted(zip(reward1, reward2), key = lambda p : p[1] - p[0])\n",
    "        return sum(x for x, _ in a[:k]) + sum(y for _, y in a[k:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        diff = [(reward1[i] - reward2[i], reward2[i]) for i in range(len(reward1))]\n",
    "        diff.sort(key = lambda x : -x[0])\n",
    "        res = 0\n",
    "        for i in range(len(diff)):\n",
    "            if i < k:\n",
    "                res += diff[i][0] + diff[i][1]\n",
    "            else:\n",
    "                res += diff[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        newlst = [(reward1[i], reward2[i]) for i in range(len(reward1))]\n",
    "        sorted_newlst = sorted(newlst, key=lambda x: -(x[0]-x[1]))\n",
    "        return sum([x[0] for x in sorted_newlst[:k]] + [x[1] for x in sorted_newlst[k:]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        diff = []\n",
    "        for i in range(len(reward1)):\n",
    "            diff.append((reward2[i]-reward1[i], i))\n",
    "        diff.sort()\n",
    "        res = sum(reward2)\n",
    "        for i in range(k):\n",
    "            res -= diff[i][0]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        diff = [0] * n\n",
    "        for i, (x, y) in enumerate(zip(reward1, reward2)):\n",
    "            diff[i] = (x - y, i)\n",
    "        diff.sort()\n",
    "        ans = 0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if n - i <= k:\n",
    "                ans += reward1[diff[i][1]]\n",
    "            else:\n",
    "                ans += reward2[diff[i][1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        diff = [(reward2[i]-reward1[i],i) for i in range(len(reward1))]\n",
    "        diff.sort()\n",
    "        res = 0\n",
    "        for i in range(len(diff)):\n",
    "            if i < k:\n",
    "                res += reward1[diff[i][1]]\n",
    "            else:\n",
    "                res += reward2[diff[i][1]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        reward = [(reward1[i] - reward2[i], i) for i in range(len(reward1))]\n",
    "        ans = 0\n",
    "        reward.sort(key=lambda x: x[0])\n",
    "        for i in range(len(reward)):\n",
    "            _, index = reward[i]\n",
    "            if i < len(reward) - k:\n",
    "                ans += reward2[index]\n",
    "            else:\n",
    "                ans += reward1[index]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        lenght = len(reward1)\n",
    "        reward1_ = sorted([(reward1[i]-reward2[i], i) for i in range(lenght)],\n",
    "                            key=lambda item: item[0], reverse=True)\n",
    "        res = 0\n",
    "        for _, r_i in reward1_:\n",
    "            if k:\n",
    "                res += reward1[r_i]\n",
    "                k -= 1\n",
    "            else:\n",
    "                res += reward2[r_i]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        dis = [i-j for i,j in zip(reward1, reward2)]\n",
    "        res = sorted(zip(dis, range(0,len(reward1))), reverse=True)\n",
    "        return sum([i for i,_ in res[:k]]) + sum(reward2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        dis = [i-j for i,j in zip(reward1, reward2)]\n",
    "        res = sorted(zip(dis, range(0,len(reward1))), reverse=True)\n",
    "        return sum([i for i,_ in res[:k]]) + sum(reward2)\n",
    "        index = set([j for _,j in res[:k]])\n",
    "        return sum([reward1[i] if i in index else reward2[i] for i in range(0, len(reward1))])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n = len(reward1)\n",
    "        temp = []\n",
    "        for i in range(n):\n",
    "            temp.append([i, reward1[i] - reward2[i]])\n",
    "        temp = sorted(temp, key=lambda x: x[1], reverse=True)\n",
    "        s = []\n",
    "        for i in range(k):\n",
    "            reward2[temp[i][0]] = reward1[temp[i][0]]\n",
    "        \n",
    "        return sum(reward2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        lenght = len(reward1)\n",
    "        reward1_ = [(reward1[i]-reward2[i], i) for i in range(lenght)]\n",
    "        reward1_.sort(key=lambda item: item[0], reverse=True)\n",
    "        print(reward1_)\n",
    "        res = 0\n",
    "        for i, (_, r_i) in enumerate(reward1_):\n",
    "            if k:\n",
    "                res += reward1[r_i]\n",
    "                k -= 1\n",
    "            else:\n",
    "                res += reward2[r_i]\n",
    "            # if k==0:\n",
    "            #     res += reward2[r_i]\n",
    "            # elif i+k == lenght:\n",
    "            #     res += reward1[r_i]\n",
    "            #     k -= 1\n",
    "            # elif reward1[r_i] >= reward2[r_i]:\n",
    "            #     res += reward1[r_i]\n",
    "            #     k -= 1\n",
    "            # else:\n",
    "            #     res += reward2[r_i]\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        n=len(reward1)\n",
    "        ls=[[] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            ls[i].append(reward1[i]-reward2[i])\n",
    "            ls[i].append(i)\n",
    "        ls.sort(key= lambda i:i[0])\n",
    "        r=sum(reward2)\n",
    "        for i in range(n):\n",
    "            if i>=n-k:\n",
    "                r+=ls[i][0]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        reward = [(i, r1 - r2) for i, (r1, r2) in enumerate(zip(reward1, reward2))]\n",
    "        reward = sorted(reward, key=lambda x: x[1], reverse=True)\n",
    "        print(reward)\n",
    "        best_reward = 0\n",
    "        for i in range(k):\n",
    "            best_reward += reward1[reward[i][0]]\n",
    "        for i in range(k, len(reward1)):\n",
    "            best_reward += reward2[reward[i][0]]\n",
    "        \n",
    "        return best_reward"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        length = len(reward1)\n",
    "        reward = [[reward1[x], reward2[x]] for x in range(0, length)]\n",
    "        for x in reward:\n",
    "            x.append(x[1] - x[0])\n",
    "        answer = 0\n",
    "\n",
    "        mouse2 = length - k\n",
    "        if mouse2 > 0:\n",
    "            reward = list(sorted(reward, key=lambda x:x[2], reverse=True))\n",
    "            stack = []\n",
    "            idx = 0\n",
    "            while mouse2 > 0 and idx < length:\n",
    "                answer += reward[idx][1]\n",
    "                stack.append(idx)\n",
    "                mouse2 -= 1\n",
    "                idx += 1\n",
    "            while stack:\n",
    "                del reward[stack.pop(-1)] \n",
    "        \n",
    "        mouse1 = k\n",
    "        reward = list(sorted(reward, key=lambda x:x[0], reverse=True))\n",
    "        for x in reward:\n",
    "            if mouse1 == 0:\n",
    "                break\n",
    "            answer += x[0]\n",
    "            mouse1 -= 1\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        memo = []\n",
    "        n = len(reward1)\n",
    "        for i,j in enumerate(reward1):\n",
    "            memo.append([i, reward1[i] -reward2[i]])\n",
    "        memo = sorted(memo, key=lambda x:x[1], reverse=True)\n",
    "        print(memo)\n",
    "        res = sum(reward2)\n",
    "        for i in range(k):\n",
    "            res += memo[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:\n",
    "        ta=[]\n",
    "        if k==0:return sum(reward2)\n",
    "        for pos in range(len(reward1)):\n",
    "            ta.append((pos,reward1[pos]-reward2[pos]))\n",
    "        ta.sort(key=lambda x:-x[1])\n",
    "        s=0\n",
    "        cnt=0\n",
    "        s2=set()\n",
    "        for e in ta:\n",
    "            s+=reward1[e[0]]\n",
    "            s2.add(e[0])\n",
    "            cnt+=1\n",
    "            if cnt==k:break\n",
    "        if cnt<len(reward2):\n",
    "            for pos in range(len(reward2)):\n",
    "                if pos not in s2:\n",
    "                    s+=reward2[pos]\n",
    "        return s\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
